//在数组中的两个数字，如果前面一个数字大于后面的数字，(要看后面所有的)
// 则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。
// 并将P对1000000007取模的结果输出。 即输出P mod 1000000007
/*public class Solution1 {
    //这个方法时间复杂度太高
    public int InversePairs0(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int tmp = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < tmp) {
                    count++;
                }
            }
        }
        return count % 1000000007;
    }
}*/
public class Solution{
    //使用归并的方法
    //定义一个成员变量 存储逆序对的数量
    int count = 0;
    //计算数组中逆序对数量
    public int InversePairs(int[] nums){
        //如果数组长度小于2 不存在 逆序对，返回0
        if(nums.length < 2){
            return 0;
        }
        mergeSort(nums,0,nums.length-1);
        return count;
    }
    //归并排序的递归实现
    public void mergeSort(int[] nums,int left,int right){
        //找到分割点 避免（left+right)/2可能导致的整数溢出
        int mid = left+(right - left) / 2;
        //如果左边界小于有边界，说明还有子数组需要排序
        if(left < right){
            //对左子数组进行归并递归
            mergeSort(nums,left,mid);
            //对右子数组进行归并递归
            mergeSort(nums,mid+1,right);
            //合并两个已排序的数组，并计算逆序对
            merge(nums,left,mid,right);
        }
    }
    public void merge(int[] nums, int left, int mid, int right){
        //创建一个临时数组，用于存储合并后的有序元素
        int[] arr = new int[right - left +1];
        //初始化临时数组的下标
        int c = 0;
        //保存原数组中当前合并区域的起始下标
        int s = left;
        //左子数组的起始指针
        int l = left;
        //右子树组的起始地址
        int r = mid + 1;
        //当左子数组和右子树组还有元素的时候，进行合并
        while(l <= mid && r <= right){
            //如果左子数组的当前元素小于右子树组的当前元素
            if(nums[l] <= nums[r]){
                //将左子数组的当前元素放入临时数组
                arr[c] = nums[l];
                //移动临时数字的下标和左子数组的指针
                c++;
                l++;
            }else{//否则，左子数组的当前元素大于右子树组的当前元素
                //将右子树组的当前元素放入临时数组
                arr[c] = nums[r];
                //此时，左子数组的当前元素及其后面的所有元素（直到中点mid）
                //都与右子树组的当前元素构成了逆序对
                //因此，逆序对的数量增加mid+1-l（左子树）
                count += mid + 1 - l;
                //为了防止溢出，对count取模
                count %= 1000000007;
                //移动临时数组的小标和右子树组的指针
                c++;
                r++;
            }
        }
        //如果左子数组还有剩余元素，将他们全部都放入临时数组
        while(l <= mid){
            arr[c++] = nums[l++];
        }
        //如果右子数组还有剩余元素，将它们全部放入到临时数组
        while(r <= right){
            arr[c++] = nums[r++];
        }
        //将临时数组中的有序元素复制回原数组的指定位置
        for(int num : arr){
            nums[s++] = num;
        }
    }
}
